Many problems in Artificial Intelligence and combinatorial search applications are formulated as constraint-satisfaction problems. Briefly stated, a solution of a constraint-satisfaction problem typically requires that an arbitrary set of constraints be satisfied. A search procedure is employed to enumerate all solutions that simultaneously satisfy all constraints on the problem.
Solution techniques that have been developed for this class of problems include the backtrack search algorithm. An example is found in a journal article entitled "Backtrack programming", Journal of the ACM, Vol. 12, 1965, pp. 516-524 by S. Golomb et al.
More efficient variations of this backtrack search algorithm are found in the following journal articles A. K. Mackworth, "Consistency in Networks of Relations", Artificial Intelligence, Vol. 8, pp. 99-118, 1977; R. M. Haralick and L. G. Shapiro, "The Consistent Labeling Problem: Part I", IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 1, Apr. 1979, pp. 173-184; R. M. Haralick and G. L. Elliott, "Improving Tree Search Efficiency for Constraint Satisfaction Problems", Artificial Intelligence pp. 263-313, 1980; and J. R. Bitner and E. M. Reingold, "Backtrack Programming Techniques", Comm. of the ACM, Vol. 18, pp. 651-656, 1975.
Prior multiprocessor search algorithms typically attempt to divide the search space into subspaces that are searched in parallel by multiple processors. One disadvantage inherent in known conventional multiprocessor search algorithms is that the speedup tends to fall away from linear, i.e., saturate as the number of processors is increased. The primary reason for this saturation is related to the length of the longest running search task. A large variance in the task running times can lead to significant imbalance on the processing load placed on the different processors. This can result in a considerable amount of time being wasted by some processors while waiting for the processor executing the longest search task to finish.
In order to achieve a desired level of processing efficiency it is important that the processing task be allocated amongst the various processors such all processors finish at substantially the same time. If the processing load is well balanced, then no processor idles for an unduly long period while waiting for other processors to finish work. As a result processing speedups and efficiencies are realized over the load-imbalanced system.
It is thus one object of the invention to provide apparatus and method for allocating processing tasks that explicitly takes into account and overcomes the saturation effect.
It is another object of the invention to provide apparatus and method that overcomes the saturation effect by assigning processors in proportion to an amount of search effort in different subtrees of a search tree.
It is a further object of the invention to minimize, in a multiprocessor system, a variance in a search effort along different subtrees of a backtrack search tree employed for solving an instance of a constraint-satisfaction problem such that all processors finish their respective processing tasks at substantially the same time.